백준 9252번 - LCS 2

문제링크

백준 9251번 - LCS 의 역추적이 추가된 버전이다.
LCS의 길이를 구하는 것 + LCS를 구하는 문제

LCS를 직접 구해야하기 때문에 백준 9251번 - LCS 처럼 1차원 배열로 풀 수 없다.
2차원 배열로 흔적을 남겨놔야한다.

코드

틀린코드

const readline=require("readline")

const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
})

let input=[]

rl.on("line",(line)=>{
    input.push(line)
})

rl.on("close",()=>{
    const a=input[0]
    const b=input[1]

    const dp=new Array(b.length).fill(null).map(()=>new Array(a.length).fill(0))


    for(let i=0;i<b.length;i++){
        for(let j=0;j<a.length;j++){
            if(a[j]==b[i]){
                dp[i][j]=i==0||j==0? 1 : dp[i-1][j-1]+1
            }
            else{
                dp[i][j]=Math.max(i==0? 0 : dp[i-1][j],j==0? 0: dp[i][j-1])
            }
        }
    }

    let result=[]
    let x=b.length-1
    let y=a.length-1
    while(true){
        const cur=dp[x][y]
        if(x>0 && dp[x-1][y]==cur){
            x--;
        }
        else if(y>0 && dp[x][y-1]==cur){
            y--;
        }
        else{
            result.push(b[x])
            x--;
            y--;
        }
        if(x<0 || y<0){
            break
        }
    }
    console.log(result.length)
    console.log(result.reverse().join(""))
})

처음에 이렇게 풀었는데 틀렸다.
이유는 즉슨, 역추적하는 과정에서 조건이 잘못됐다.

1. 범위를 벗어나지 않는다.(x<0 || y<0)
2. 역추적이 끝난다.(dp[x][y] == 0)

2번의 조건을 추가해주지 않아서 틀렸다.

정답 코드

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

rl.on("line", (line) => {
    input.push(line);
});

rl.on("close", () => {
    const a = input[0], b = input[1];
    const dp = Array.from({ length: b.length }, () => Array(a.length).fill(0));

    for (let i = 0; i < b.length; i++) {
        for (let j = 0; j < a.length; j++) {
            if (b[i] === a[j]) {
                dp[i][j] = (i > 0 && j > 0) ? dp[i - 1][j - 1] + 1 : 1;
            } else {
                dp[i][j] = Math.max(i > 0 ? dp[i - 1][j] : 0, j > 0 ? dp[i][j - 1] : 0);
            }
        }
    }

    let x = b.length - 1, y = a.length - 1;
    let result = [];

    while (x >= 0 && y >= 0 && dp[x][y] > 0) {
        if (x > 0 && dp[x - 1][y] === dp[x][y]) {
            x--;
        } else if (y > 0 && dp[x][y - 1] === dp[x][y]) {
            y--;
        } else {
            result.push(b[x]);
            x--;
            y--;
        }
    }

    console.log(result.length);
    console.log(result.reverse().join(""));
});

정제 코드

dp 배열에 테두리 공백을 만들고 조건을 dp 값이 아닌 해당 비교값이 같은지로 하면 더 정제될 수 있다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

rl.on("line", (line) => {
    input.push(line.trim());
});

rl.on("close", () => {
    const strA = input[0];
    const strB = input[1];
    const lenA = strA.length;
    const lenB = strB.length;

    // DP 테이블 초기화
    const dp = Array.from({ length: lenB + 1 }, () => new Array(lenA + 1).fill(0));

    // LCS 길이 계산
    for (let i = 1; i <= lenB; i++) {
        for (let j = 1; j <= lenA; j++) {
            dp[i][j] = strB[i-1] === strA[j-1]
                ? dp[i-1][j-1] + 1
                : Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // LCS 역추적
    let lcs = [];
    let i = lenB, j = lenA;
    while (i > 0 && j > 0) {
        if (strB[i-1] === strA[j-1]) {
            lcs.push(strB[i-1]);
            i--;
            j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    console.log(lcs.length);
    lcs.length > 0 && console.log(lcs.reverse().join(''));
});